Встраивание функций

В вычислительной технике встраивание функций (англ. Inlining) — способ оптимизации, при котором вызов функции заменяется непосредственно её телом. Встраивание функций аналогично по сути подстановке из макроса, но в отличие от неё не изменяет исходный код и происходит во время компиляции, в то время как макросы изменяют исходный код перед компиляцией.

Встраивание функций — это важная оптимизация, однако оказываемый эффект на производительность может быть различным. Как правило, некоторое количество встраиваний помогает улучшить быстродействие при очень незначительных затратах пространства, но избыточность использования может замедлить программу из-за того, что встроенный код станет потреблять слишком много кэша инструкций, а также займёт значительное количество пространства. В книге Jones & Marlow 1999 года приведён обзор академической литературы 1980-х и 1990-х годов по встраиванию функций.

Обзор

Встраивание функций аналогично раскрытию макросов — по сути компилятор помещает новую копию функции в каждое место, где она вызывается. Код со встроенными функциями работает немного быстрее обычного, поскольку пропадают дополнительные действия по вызову функций, однако же при этом увеличивается расход памяти. Если функция встроена 10 раз, то в код будет вставлено 10 копий функции. Поэтому встраивание лучше всего подходит для небольших часто используемых функций. В C++ по умолчанию встраиваемыми являются методы, определённые в описании класса (нет необходимости использовать ключевое слово inline); в противном случае ключевое слово необходимо. Компилятор может проигнорировать попытку программиста объявить функцию встраиваемой — в основном это актуально для очень больших функций.

Встраивание функций используется для экономии процессорного времени, затрачиваемого на вызов функции. Как правило используется для часто исполняемых функций. Методика также позволяет сэкономить память для очень малых функций, кроме того она делает возможным применение иных оптимизаций.

Без указаний о встраивании компилятор зачастую сам решает, какие функции следует встроить. Программист практически не контролирует, какие функции станут встраиваемыми. Если программист сам решает вопросы встраивания функций, он может использовать знания о работе конкретного приложения для лучшей оптимизации.

При вызове функции, управление передаётся в её тело при помощи инструкции ветвления (branch) или инструкции вызова (call). Встраивание даёт возможность избавиться от этих инструкций — в этом случае управление переходит непосредственно к коду функции.

Как правило компиляторы используют встраивание для реализации некоторых операторов. К примеру тела и условия циклов необходимо вычислять непосредственно при исполнении. Это достигается встраиванием кода для вычисления условий и тела циклов в место их вызовов. Встраивание операторов также помогает повысить производительность.

Если рассматривать это в контексте функциональных языков программирования, за встраиванием функций обычно следует преобразование бета-редукции.

Программист может вручную встроить функцию, скопировав её код и вставив его в местах вызова. Однако же другие методы управления встраиванием(см. ниже) являются более предпочтительными, поскольку не вызывают ошибок, возникающих, если программист при исправлении ошибки во встраиваемой функции не обновит какой-то из её дубликатов.

Оказываемый эффект на производительность

Основной эффект от этой оптимизации заключается в повышении быстродействия (за счёт устранения расходов на вызовы) и в увеличении расхода памяти (из-за дублирования тела функции). Расход памяти за счёт дублирования кода доминирует, за исключением простых случаев. Таким образом, основной эффект от встраивания заключается в ускорении кода за счёт пространства.

Однако главным преимуществом встраивания является возможность дальнейших оптимизаций и улучшения планирования за счёт увеличения размера тела функции, поскольку для более крупные функции можно оптимизировать удачнее. Полностью оценить влияние на производительность довольно сложно из-за большого количества эффектов на систему памяти (в первую очередь на кэша инструкций), которая оказывает значительное влияние на производительность современных процессоров. Встраивание определённых функций в зависимости от конкретной программы и кэша может как увеличивать так и уменьшать производительность.

Влияние встраивания также зависит от языка программирования, из-за различных уровней абстракции. В императивных языках более низкого уровня, таких как C и Fortran, можно достичь увеличения скорости на 10-20% с незначительным влиянием на размер кода. В более абстрактных языках эффект может быть значительно выше из-за количества слоёв, которые удаляет встраивание. В качестве примера можно привести язык Self, где за счёт встраивания удавалось достичь коэффициентов ускорения от 4 до 55.

Непосредственная выгода от устранения вызова функции заключается в следующем:

• Устраняются инструкции, необходимые для вызова функции, как в вызывающей функции, так и в вызываемом объекте. Это код для размещения аргументов в стеке или в регистрах, сам вызов функции, пролог функции, в конце тела эпилог функции, оператор возврата, извлечение возвращаемого значения, удаление аргументов из стеков и (при необходимости) восстановление регистров.
• Упрощается задача распределения регистров поскольку не нужно задействовать регистры для передачи аргументов .
• Устраняется необходимость передавать ссылки, а затем разыменовывать их при вызовах по ссылке (или при вызовах по соиспользованию).

Однако, основная выгода от встраивания заключается в предоставляемых этим возможностях дальнейшей оптимизации. Оптимизации кода из нескольких функций могут быть выполнены без необходимости межпроцедурной оптимизации (IPO): после встраивания в расширенном теле функции возможны дополнительные «внутрипроцедурные» («глобальные») оптимизации. К примеру:

• Константа, переданная в качестве аргумента, может быть присвоена всем соответствующим параметрам. Часть функции (инвариант цикла) может быть «вынута» из цикла.
• Задача распределения регистров может быть эффективнее решена в более крупном теле функции.
• Высокоуровневые оптимизации, такие как Escape-анализ, могут выполняться в большем объёме и быть более эффективными, особенно если компилятор в процессе оптимизации полагается, в первую очередь, на внутрипроцедурный анализ.

Такие оптимизации могут быть выполнены и без встраивания, но требуют значительно более сложных компиляторов и компоновщиков (в том случае, если вызов и реализация находятся в отдельных единицах компиляции).

В некоторых случаях, однако, спецификация языка позволяет программам делать дополнительные предположения относительно аргументов процедур. После встраивания эта информация может быть утеряна, делая невозможными некоторые оптимизации. Более умные компиляторы (такие как компилятор Haskell из Глазго) будут отслеживать это, но простая реализация встраивания не будет этого учитывать.

Для системы памяти от встраивания можно выделить следующую пользу:

• При устранении ветвления и расположении исполняемого кода близко в памяти повышается производительность кэша команд за счет улучшения ссылочной локальности (из-за сопредельности и прямой последовательности инструкций). Эффект значительный, хотя и меньший, чем у специально предназначенных для сопредельности оптимизаций.

Прямые затраты на встраивание заключаются в увеличении размера кода из-за дублирования тела функции в каждом месте вызова. Этих затрат нет только в случае очень маленьких функций, где тело функции меньше затрат на вызов (вызов, обработка аргументов и возвращаемых значений), таких как тривиальный метод доступа (геттеры и сеттеры); или для функций, которые используются лишь единожды. Поэтому при оптимизации по размеру (часто необходимой во встраиваемых (embedded) системах), эта методика оптимизации может быть сведена к минимуму или не использоваться.

Встраивание также ухудшает производительность из-за расширения (дублирования) кода, снижающего производительность кэша инструкций. Замедление заметнее всего, если до расширения рабочий объём программы (т.н. горячий раздел кода) помещается на одном уровне иерархии памяти (например, в кэше 1 уровня), а после расширения он больше не вмещается туда, что приводит к частым промахам в кэш на этом уровне. Из-за существенной разницы в производительности на разных уровнях иерархии кэша это замедляет работу кода. На высшем уровне иерархии это может привести к увеличению количества отказов страниц (page faults), катастрофическому снижению производительности из-за пробуксовок (thrashing) и даже полному отказу программы. Последнее редко встречается в обычных настольных и серверных приложениях, где размер кода невелик по отношению к доступной памяти, однако может быть проблемой для сред с ограниченными ресурсами (напр. для встроенных систем). Один из способов решения состоит в том, чтобы разделить код функции на короткий горячий (быстрый) путь со встраиваниями и длинный холодный (медленный) путь без встраиваний.

Основной вред встраивания для производительности в первую очередь актуален для больших функций, которые используются во многих местах. Однако определение точки безубыточности, за которой встраивание снижает производительность, является сложным и зависит от реальной нагрузки. Для граничных случаев это может быть вопросом ручной оптимизации или оптимизации с помощью профилирования. Аналогичная проблема возникает и с другими расширяющими оптимизациями, такими как размотка цикла: несмотря на уменьшение количества инструкций, производительность может уменьшится из-за более медлительного кэша.

Сложно точно оценить влияние встраивания на производительность кэша. При небольших размерах кэша (значительно меньших, чем рабочий объём до расширения), доминирует эффект от увеличения последовательности, поэтому встраивание улучшает производительность кэша. Если размер кэша близок к рабочему объёму, то производительность кэша снижается за счёт того, что расширенный после встраивания код не вмещается в кэш. При размерах кэша, превышающих рабочий объём, встраивание оказывает незначительное влияние на производительность кэша. Кроме того некоторые улучшения в конструкции кэша (такие как переадресация нагрузки (load forwarding)), могут нивелировать увеличение количества промахов в кэш.

Поддержка в компиляторах

Компиляторы используют различные способы, чтобы решить какие функции стоит встроить; среди них имеют значение как явные указания от программистов для конкретных функций, так и общие указания из параметров командной строки. Во многих компиляторах на многих языках автоматическое встраивание основывается на суждении о том, является ли оно полезным; в других случаях оно может быть задано вручную директивами компилятора или с использованием ключевого слова inline. Это ключевое слово лишь указывает на то, что функцию желательно встраивать - значимость этого указания варьируется в зависимости от языка и компилятора.

Разработчики компиляторов учитывают вышеупомянутые проблемы и реализуют в своих компиляторах различные эвристики, подбирающие функции, которые следует встраивать, чтобы в большинстве случаев это улучшало производительность, а не ухудшало её.

Реализация

Реализация встраивания компилятором обычно довольно проста. В зависимости от того, проводится ли эта операция в коде на разных языках, компилятор может выполнять встраивание либо в высокоуровневой промежуточной форме (например, в абстрактное синтаксическое дерево), либо в низкоуровневую промежуточную форму. В любом случае компилятор просто вычисляет аргументы, сохраняет их в переменных, соответствующих аргументам функции, а затем вставляет тело функции в место вызова.

Компоновщик также может встраивать функции, исходный код которых недоступен, например библиотечные функции (см. оптимизация во время компоновки). Среда выполнения тоже может встраивать функции во время выполнения. Такие среды, как Java Hotspot используют информацию динамического профилирования для принятия решения о том, какие функции следует встроить.

Вот простой пример встраивания, выполняемого «вручную» на уровне исходника в языке Cи:

int pred(int x)
{
    if (x == 0)
        return 0;
    else
        return x - 1;
}

До встраивания:

int func(int y) 
{
    return pred(y) + pred(0) + pred(y+1);
}

После встраивания:

int func(int y) 
{
    int tmp;
    if (y   == 0) tmp  = 0; else tmp  = y - 1;       /* (1) */
    if (0   == 0) tmp += 0; else tmp += 0 - 1;       /* (2) */
    if (y+1 == 0) tmp += 0; else tmp += (y + 1) - 1; /* (3) */
    return tmp;
}

Обратите внимание, что это только пример. В реальном приложении на языке Си было бы предпочтительнее использовать функционал для встраивания, например как параметризованный макрос или встроенную функцию чтобы компилятор сам преобразовал код таким образом. В следующем разделе перечислены способы оптимизации этого кода.

Встраивание в макросах ассемблера

Макросы в языке ассемблера предлагают альтернативный подход к встраиванию, при котором последовательность инструкций генерируется при "раскрытии" некоего исходного оператора-макрокоманды (с нулём или более параметров). Один из параметров может указывать, чтобы вместо последовательности инструкций генерировалась отдельная одноразовая подпрограмма, содержащая нужную последовательность, которая вызывалась бы вместо встроенного кода. Пример:

MOVE FROM=array1,TO=array2,INLINE=NO

Эвристики

Проводились исследования целого ряда различных эвристик для встраивания. Обычно алгоритму встраивания предоставляется определённый бюджет пространства (допустимое увеличение размера программы). Алгоритм стремится встроить наиболее ценные вызовы, не превысив этого бюджета. В этом смысле многие алгоритмы встраивания обычно моделируют решение задачи о рюкзаке. Чтобы решить, какие места вызовов являются наиболее ценными, встроенный алгоритм должен оценить их пользу — т. е. ожидаемое сокращение времени исполнения. Обычно для оценки пользы используются данные профилирования о частоте выполнения различных путей кода.

Кроме данных профилирования, современные динамические компиляторы применяют несколько более продвинутых эвристик, таких как:

• Оценка того, какие пути исполнения приведут к наибольшему росту быстродействия (при включении дополнительных оптимизаций компилятора после встраивания) и увеличение уровня выгоды от таких путей для алгоритма.
• Адаптивная корректировка порога безубыточности встраивания на основе размера единицы компиляции и объёма уже встроенного кода.
• Группировка подпрограмм в кластеры и встраивание целых кластеров вместо отдельных подпрограмм. В этом случае эвристика подбирает кластеры, группируя методы, для которых встраивание правильного подмножества кластера приводит к худшей производительности, чем отсутствие встраивания.

Выгоды

Встраивание само по себе уже является оптимизацией, поскольку оно устраняет расходы на вызов, однако его главное достоинство состоит в том, что это содействующая оптимизация. Это значит, что после встраивания тела функции в месте вызова (нередко с аргументами, которые могут быть фиксированными константами) у компилятора появляется возможность проводить невозможные ранее преобразования. К примеру может оказаться, что условие в операторе ветвления всегда истинно (или всегда ложно) для этого конкретного места вызова. Это, в свою очередь, приводит к устранению мёртвого кода, выделению инвариантного кода из цикла или удалению индуктивной переменной.

В вышеприведённом примере на языке СИ, предостаточно возможностей для дальнейшей оптимизации. Компилятор может произвести нижеследующие действия:

• Операторы tmp += 0 в строках, отмеченных (2) и (3), ничего не делают. Компилятор может удалить их.
• Условие 0 == 0 всегда истинно, поэтому компилятор может заменить строку (2), на tmp += 0 (которая ничего не делает).
• Компилятор может переписать условие y+1 == 0 на y == -1.
• Компилятор может сократить выражение (y + 1) - 1 до просто y.
• Выражения y и y+1 не могут быть равны нулю. Это позволяет компилятору исключить одну проверку.
• В операторах вида if (y == 0) return y значение y известно в теле и может быть встроено.

В результате функция станет выглядеть так:

int func(int y) 
{
    if (y == 0)
        return 0;
    if (y == -1)
        return -2;
    return 2*y - 1;
}

Ограничения

Полное встраивание не всегда возможно из-за рекурсии: рекурсивное встраивание вызовов никогда не завершится. Существуют различные решения этой задачи, к примеру встраивание до определённой границы или анализ графа вызовов и разрыв циклов в определённых узлах (т. е. прекращение цикла встраиваний в некоторых местах). Аналогичная проблема возникает при раскрытии макрокоманд - рекурсивное раскрытие никогда не заканчивается. Как правило, это решается простым запретом на использование рекурсивных макросов (как в C и C++).

Сравнение с макросами

Традиционно в таких языках, как Си, встраивание выполнялось на уровне исходников при помощи параметризованных макросов. Возможность использовать настоящее встраивание функций, доступное в C99, даёт ряд преимуществ:

• В языке C макросы не выполняют проверку типов и даже не проверяют правильность формирования аргументов, в отличие от вызовов функций.
• В макросе языка C ключевое слово return имеет другое значение, нежели в функции (это приведёт к завершению вызывающей функции, а не завершению макроса). Иными словами, макрос не может возвращать ничего, что не является результатом последнего выражения, вызванного внутри него.
• Поскольку макросы C используют простую текстовую подстановку, это может привести к непреднамеренным побочным эффектам и неэффективности из-за пересчёта аргументов и приоритетов операций.
• Зачастую трудно понять ошибки компилятора в макросах потому что они относятся к вставленному коду, а не к коду, написанному программистом. Поэтому, отладочная информация для встроенного кода обычно полезнее, чем информация для кода с раскрытыми макросами.
• Многие конструкции неудобно или невозможно выразить с помощью макросов, или же необходим существенно другой синтаксис. Встроенные функции используют тот же синтаксис, что и обычные функции, и могут быть с лёгкостью объявлены встраиваемыми или не встраиваемыми.

Многие компиляторы могут также встраивать некоторые рекурсивные функции, а рекурсивные макросы, как правило, запрещены.

Создатель Си++, Бьёрн Страуструп, любит подчёркивать, что следует по возможности избегать макросов и рекомендует чаще пользоваться встраиваемыми функциями.

Методы подбора

Многие компиляторы агрессивно встраивают функции везде, где это выгодно. Хотя это и может привести к увеличению размера исполняемого файла, тем не менее такая агрессивная стратегия как правило окупается, поскольку объемы памяти компьютерных систем увеличиваются быстрее, чем скорость процессоров. Встраивание - это критически важная оптимизация для функциональных и объектно-ориентированных языков программирования: как правило в них применяются функции небольшого размера, а встраивание позволяет обеспечить им достаточный контекст для того, чтобы классическая оптимизация была эффективной.

Поддержка в языках программирования

Многие языки, включая Java и функциональные языки, не предоставляют языковых конструкций для встраивания функций, но их компиляторы или интерпретаторы автоматически агрессивно встраивают функции. Другие языки предоставляют синтакс для явных указаний, как правило в виде директив компилятора (прагм).

В языке программирования Aда существует директива для встроенных функций.

В языке Common Lisp можно определять функции встраиваемыми при помощи объявления inline:

 (declaim (inline dispatch))
 (defun dispatch (x)
   (funcall
     (get (car x) 'dispatch) x))

Компилятор GHC языка Haskell автоматически пытается встраивать достаточно малые функции, однако же возможно использовать прямо указать на необходимость встраивания при помощи директивы:

key_function :: Int -> String -> (Bool, Double)
{-# INLINE key_function #-}

C and C++

В языках C и C++ есть ключевое словоinline. Оно функционирует одновременно как директива компилятора, указывая, что встраивание является «желательным», но не «обязательным», а также изменяет видимость функции и поведение компоновщика. Изменение видимости необходимо для того, чтобы функция могла быть встроена при помощи стандартного набора инструментов C: где компиляция отдельных файлов (или единиц трансляции) предшествует компоновке. Поэтому чтобы компоновщик мог встраивать функции, они должны быть объявлены в заголовке (чтобы быть видимыми) и помечены inline (чтобы избежать двусмысленности из-за нескольких определений).

См. также

• Макрокоманда
• Частичные вычисления
• Хвостовая рекурсия

Внешние ссылки

• "Устранение виртуальных вызовов функций в программах на C++ (Eliminating Virtual Function Calls in C++ Programs)", Жеральд Эгнер(Gerald Aigner) и Урс Хёльцле(Urs Hölzle)
• "Снижение затрат на косвенные вызовы функций в программах на C++ (Reducing Indirect Function Call Overhead In C++ Programs)", Брэд Кэлдер(Brad Calder) и Дирк Грюмвальд(Dirk Grumwald)
• ALTO - оптимизация во время компоновки для DEC Alpha(ALTO - A Link-Time Optimizer for the DEC Alpha)
• "Продвинутые способы (Advanced techniques)", Джон Р. Левин
• "Полная оптимизация программы на Visual C++ .NET (Whole Program Optimization with Visual C++ .NET)", Брэндон Брэй(Brandon Bray)